package com.liuyubo.sort;

import java.util.Arrays;

public class QuickSort implements Sort {
    @Override
    public void sort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private void quickSort(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }

        int p = partition(arr, l, r);
        quickSort(arr, l, p - 1);
        quickSort(arr, p + 1, r);
    }

    /**
     * 对arr[l...r]部分进行partition操作
     * @param arr   数组
     * @param l     左边界
     * @param r     有边界
     * @return      返回p，使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
     */
    private int partition(int[] arr, int l, int r) {
        int v = arr[l];
        // arr[l+1...j] < v ; arr[j+1...i)] > v
        int j = l;
        for (int i = l + 1; i <= r;i++) {
            if (arr[i] < v) {
                swap(arr, ++j, i);
            }
        }
        swap(arr, l, j);
        return j;
    }

    @Override
    public String getName() {
        return "Quick Sort";
    }

    public static void main(String[] args) {
        int[] arr = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        QuickSort sort = new QuickSort();
        sort.sort(arr);
        Arrays.stream(arr).forEach(System.out::println);
    }
}
